﻿//描述
//你有一个背包，最多能容纳的体积是V。
//现在有n种物品，每种物品有任意多个，第i种物品的体积为vi, 价值为wi。
//（1）求这个背包至多能装多大价值的物品？
//（2）若背包恰好装满，求至多能装多大价值的物品？
//
//输入描述：
//	第一行两个整数n和V，表示物品个数和背包体积。
//	接下来n行，每行两个数vi和wi，表示第i种物品的体积和价值。1≤n, V≤1000
//
//输出描述：
//	输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
//
//输入：
//	2 6
//	5 10
//	3 1
//输出：
//	10
//	2
//
//输入：
//	3 8
//	3 10
//	9 1
//	10 1
//输出：
//	20
//	0
//说明：
//无法恰好装满背包。
//
//输入：
//	6 13
//	13 189
//	17 360
//	19 870
//	14 184
//	6 298
//	16 242
//输出：
//	596
//	189
//说明：
//可以装5号物品2个，达到最大价值298 * 2 = 596，若要求恰好装满，只能装1个1号物品，价值为189.

#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() {
    //读⼊数据
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    //搞定第⼀问
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    cout << dp[n][V] << endl;
    //第⼆问
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    memset(dp, 0, sizeof dp);
    for (int j = 1; j <= V; j++) dp[0][j] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}